Some interleaved memories contain banks that when one of the individually addressable data cells of the bank is accessed for a cache line, the bank activates the entire row of cells which includes the accessed cell. Generally, each bank holds only one or a few of its rows currently active, holding the row active for an indefinite amount of time from when the cell was first accessed to cause the row to become active until another cell is accessed to cause another one or more rows of the bank to become active. Thus, after initial use, each bank holds some one or more of its rows active as “partially accessed”.
The purpose for holding a row active is that a cell is more quickly accessed if it is in a row that is already active. This feature is particularly useful where cache lines of related data are stored in data cells of a single row. Thus, accessing a single data cell to store a cache line in a cache also activates all other data cells of the row for possible quicker access. Consequently, a memory containing a plurality of banks, each with partial access capability, can access a number of cells more quickly than all its other cells; the number of cells ready for quick access being equal to the memory's total number of banks times the total number of active rows of each bank times the number of cells in each of the memory's rows.
Examples of memory banks with partial access capability include Extended Data Out Dynamic Random Access Memories (EDO DRAMs) and Fast Page Mode Dynamic Random Access Memories (FOP DRAMs), in which a row of the DRAM is kept charged while performing multiple reads or writes so that successive reads or writes within the row do not suffer the delay of pre-charge and access to the row.
Classical interleave patterns of memories having  banks, where =2B and B≧1, employ simple rotations through all 2B banks. Within each rotation, each successively addressed row of a memory is in a row having a same row address but in the memory's next bank, and is successively selected by simply decoding the B address bits which are usually just lower in order than the row address bits and just higher in order than the cell address bits. Thus, each rotation of a classical interleave addresses the same respective row in each successive bank successively, e.g. rows 0 of banks 0, 1, 2, . . . , −1, rows 1 of banks 0, 1, 2, . . . , −1, rows 2 of banks 0, 1, 2, . . . , −1, through rows −1 of banks 0, 1, 2, . . . , −1.
One problem with classically interleaved memories containing banks having partial access capability is that large blocks of data having some number≧2B of rows have each of their respective positions—beginning, ending and each position between—in the same banks of the memory. Because same positions of different blocks of data tend to be accessed for processing at the same time, then at different periods of time a different one of the banks of the memory tends to be the only bank being successively accessed for the data of two or more different blocks. When this happens, each of the banks in turn becomes the one being excessively accessed for cache lines in cells of different rows. Consequently, each row having just become active continually returns to being not active before another of the row's cells is accessed more quickly. Since its recognition, this problem has been only marginally solved.
The above-described problem was marginally solved by variously toggling and un-toggling one or more of the memory address's B bank-address bits, such as by using exclusive-OR (XOR) logic gates inputted by both a bank-address bit and one of the address's bits higher in order than the B bits or a single bit sum of more than one of the higher bits. The output of each gate replaced the output of the bank address bit which inputs the gate, thus replacing the bit's output for being decoded as for the classic interleave. Thus, one or more pairs of banks swapped positions in the order of rotation for the classic interleave, doing this differently for different ranges of memory's addressing. An example of this toggling technique is described in “Pseudo-Randomly Interleaved Memory,” Proceedings of the Association for Computer Machinery, September 1991 by B. R. Rau.
These solutions were only marginally successful because where a swapping helped one pair of blocks of data for accessing more data more quickly from a row already partially accessed, it often harmed another pair. Consequently, different ranges of the memory's addressing had different orders of rotation for successively addressed rows being in successively selected banks and therefore had marginal success for having some same positions of blocks in different banks. While such pseudo-random toggling improved access to some data, it caused another problem. More particularly, accessing different blocks of different clashing rotations caused some additional accessing of data of different blocks in the same bank.
A solution is needed which distributes all data positions of all blocks of data of all memory from the smallest blocks (each row of cells) up to those blocks as large as the largest pages for mapping virtual data into physical memory, statistically distributing all of them evenly (in equal numbers) and finely (every few successive addresses) among all the interleaved banks, while avoiding clashing by also preserving a consistent respective order of rotation for successively selected banks for all addressing of memory. Consider a series of consecutively addressed same-sized blocks of data, of all memory, where each block's common size is the size of any one of all the successively doubling interleaved sizes—1 row, 2 rows, 4 rows, 8 rows, etc.—through the number of rows in the largest page for virtual mapping, and the number of rows of the smallest block is no less than the number of banks of one simple rotation. Such a series of blocks will have all respectively positioned rows of the blocks—all first (beginning) rows, second rows, third rows and so on through all last (ending) rows of the blocks—residing evenly and finely in all the banks of the rotation, equal or nearly equal (differing by no more than one) numbers of rows per bank. Thus in some embodiments of the present invention, the number of rows per bank per simple rotation equals the column height occupied by representations , F, X, Y and Z in ROM 14 of each of the shunted interleaves of FIGS. 4 and 5, the occupied heights which can differ by one because of the remainder loop, but no more than one.
My aforementioned patent application Ser. No. 11/719,926 describes abbreviated interleave patterns for successively accessing plural banks in a memory to retrieve or store data interleaved among a plurality of banks. In binary embodiments, an odd number of banks are accessed by a processor during each of a plurality of abbreviated interleaves to retrieve or store data elements in the banks. Thus, as applied to a memory containing 2B banks, Q banks are accessed during each abbreviated interleave, where Q is an odd (that is, prime to the total number of banks), preferably a prime number, and 1<Q<2B. A rotation of 2B successive abbreviated interleave patterns accesses each bank 2A times, with each successive abbreviated interleave accessing a different set of Q banks also 2A times. During each interleave, each bank of a set of Q banks is accessed L times and R banks of the set of Q banks are accessed one additional time each, where 2A=L·Q+R and R=mod(2A,Q). My prior application describes a powerful technique that greatly increases the efficiency of the memory over that of the classic interleave technique for interleaving and accessing elements not via cache and that is about the same as the Ranade and Rau prime degree interleaves. It offers the advantage over the Rau and Ranade interleaves by employing a memory with 2B banks, permitting efficient binary addressing and use of the memory for paging. Also, the abbreviated interleave pattern has the efficiency of the Rau and Ranade interleaves for interleaving partially accessed rows for accessing cache lines while not having an address apparatus needing to input all physical address bits to address rows.